package com.yoshino.leetcode.improve40.fourteenth;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class CBTInserter {

    Deque<TreeNode> deque;
    TreeNode root;

    // 广度遍历
    public CBTInserter(TreeNode root) {
        deque = new LinkedList<>();
        this.root = root;
        // 遍历
        deque.offer(root);
        // 该结点需要添加元素
        while (deque.peek().left != null && deque.peek().right != null) {
            TreeNode poll = deque.poll();
            deque.offer(poll.left);
            deque.offer(poll.right);
        }
    }

    public int insert(int v) {
        TreeNode cur = deque.peek();
        if (cur.left == null) {
            cur.left = new TreeNode(v);
        } else {
            // 需要弹出
            cur.right = new TreeNode(v);
            deque.poll();
            deque.offer(cur.left);
            deque.offer(cur.right);
        }
        return cur.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter obj = new CBTInserter(root);
 * int param_1 = obj.insert(v);
 * TreeNode param_2 = obj.get_root();
 */